package com.ly.algorithm;
import java.util.*;

import org.junit.jupiter.api.Test;

import java.util.stream.Collectors;
import java.util.stream.Stream;

import static reactor.core.publisher.Flux.merge;

/**
 * @Classname TestHashMap
 * @Description TODO
 * @Date 2020/4/15 21:31
 * @Author 冷心影翼
 */
public class T {

    public static void main(String[] args) {

    }

    @Test
    public void binarySearch() {
        int[] arr = new int[]{1,-3,44,-5,6,6,7,9,11,15,33,22,77};
        System.out.println(binarySearch(arr,0,arr.length-1,6));
    }

    private int binarySearch(int[] arr,int left,int right,int target) {
        while (left<=right) {
            int mid = (left+right)/2;
            if(arr[mid] == target) {
                return mid;
            }else if(arr[mid]<target) {
                left = mid ;
            }else {
                right = mid;
            }
        }
        return -1;
    }

    @Test
    public void maopao() {
        int[] arr = new int[]{1,-3,44,-5,6,7,9,11,15,33,22,77};
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length-i-1; j++) {
                if(arr[j+1]<arr[j]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }


    @Test
    public void quickSort() {
        int[] arr = new int[]{1,-3,44,-5,5,6,6,7,9,11,15,33,22,77};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }


    private void quickSort(int[] arr, int left, int right) {
        if(left>=right) {
            return;
        }
        int p = arr[left];
        int i = left;
        int j = right;
        while (i<j) {
            while (i<j && arr[j]>=p) {
                j--;
            }
            arr[i] = arr[j];
            while (i<j && arr[i]<p) {
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = p;
        quickSort(arr,left,i-1);
        quickSort(arr,i+1,right);
    }


    @Test
    public void mergeSort() {
        int[] arr = new int[]{1,-3,44,-5,5,6,6,7,9,11,15,33,22,77};
        int[] temp = new int[arr.length];
        mergeSort(arr,0,arr.length-1,temp);
        System.out.println(Arrays.toString(arr));
    }



    private void mergeSort(int[] arr, int left, int right,int[] temp) {

        if(left<right) {
            int mid = (left+right)/2;
            mergeSort(arr,left,mid,temp);
            mergeSort(arr,mid+1,right,temp);
            merge(arr,left,mid,right,temp);
        }
    }

    private void merge(int[] arr, int left, int mid, int right,int[] temp) {
        int i = left;
        int j = mid+1;
        int t = 0;
        while (i<=mid && j<=right) {
            if(arr[i]<arr[j]) {
                temp[t++] = arr[i++];
            }else {
                temp[t++] = arr[j++];
            }
        }

        while (i<=mid) {
            temp[t++] = arr[i++];
        }

        while (j<=right) {
            temp[t++] = arr[j++];
        }

        t = 0;
        while (left<=right) {
            arr[left++] = temp[t++];
        }
    }




    @Test
    public void heapSort() {
        int[] arr = new int[]{1,-3,44,-5,5,6,6,7,9,11,15,33,22,77};
        for (int i = arr.length/2 - 1; i >= 0; i--) {
            fixDown(arr,i,arr.length);
        }

        for (int i = arr.length-1; i >=0 ; i--) {
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            fixDown(arr,0,i);
        }
        System.out.println(Arrays.toString(arr));

    }

    private void fixDown(int[] arr,int i,int heapSize) {
        int l = i*2;
        int r = i*2+1;
        int max = i;
        if(l<heapSize && arr[l] > arr[max]) {
            max = l;
        }
        if(r<heapSize && arr[r] > arr[max]) {
            max = r;
        }
        if (i!=max) {
            int temp = arr[max];
            arr[max] = arr[i];
            arr[i] = temp;
            fixDown(arr,max,heapSize);
        }
    }


    @Test
    public void t() {
    }
}
